package com.aqie.medium.sort;

import java.util.*;

/**
 * 56 合并区间 todo
 */
public class Merge {

    /**
     * 1，排序 62ms
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals.length == 0) return res.toArray(new int[0][]);
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int i = 0;
        while (i < intervals.length) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            res.add(new int[]{left, right});
            i++;
        }
        return res.toArray(new int[0][]);
    }

    /**
     * 2, O(NlogN)  95ms
     * @param intervals
     * @return
     */
    public int[][] merge2(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0)
            return new int[0][0];
        LinkedList<Interval> list = new LinkedList<>();
        for (int[] nums : intervals) {
            Interval in = new Interval(nums[0], nums[1]);
            list.add(in);
        }
        //按照区间第一个数字排序
        list.sort(Comparator.comparingInt(o -> o.num1));
        List<Interval> resList = new ArrayList<>();
        Interval first = list.removeFirst();
        while (!list.isEmpty()) {
            Interval second = list.removeFirst();
            if (first.num2 < second.num1) {
                //两个区间不相交
                resList.add(first);
                first = second;
            } else {
                //合并两个区间
                first = new Interval(first.num1, Math.max(first.num2, second.num2));
            }
        }
        resList.add(first);
        int[][] res = new int[resList.size()][2];
        for (int i = 0; i < resList.size(); i++) {
            res[i][0] = resList.get(i).num1;
            res[i][1] = resList.get(i).num2;
        }
        return res;
    }

    class Interval {
        int num1;
        int num2;

        Interval(int num1, int num2) {
            this.num1 = num1;
            this.num2 = num2;
        }
    }


    public static void main(String[] args) {
        int[][] nums = {{1,3},{2,6},{8,10},{15,18}};
    }
}
